In [2]:
from itertools import product
def all_graphs_for(n):
    nodes = list(range(n))
    index_to_edge = {}
    num_edges = 0
    for i in range(n):
        for j in range(i + 1, n):
            index_to_edge[num_edges] = (i, j)
            num_edges += 1
    
    all_edges = []
    for directions in product([0, 1], repeat=num_edges):
        edges = {}
        for i, direction in enumerate(directions):
            edges[index_to_edge[i]] = direction
        all_edges.append(edges)
    
    return nodes, all_edges
In [5]:
for i in range(2, 8):
    print(i, len(list(all_graphs_for(i)[1])), 2 ** ((i * (i - 1)) // 2))
    assert(len(list(all_graphs_for(i)[1])) == 2 ** ((i * (i - 1)) // 2))

2 2 2
3 8 8
4 64 64
5 1024 1024
6 32768 32768
7 2097152 2097152
In [28]:
from itertools import permutations

def is_equal(nodes1, edges1, nodes2, edges2):
    def direction(u, v, edges):
        if u < v:
            return edges[(u, v)]
        else:
            return 0 if edges[(v, u)] else 1
    for i in range(len(nodes1)):
        for j in range(i + 1, len(nodes1)):
            u, v = nodes1[i], nodes1[j]
            dir1 = direction(nodes1[i], nodes1[j], edges1)
            dir2 = direction(nodes2[i], nodes2[j], edges2)
            if dir1 != dir2:
                return False
    return True

def is_isometric(nodes, edges1, edges2):
    return any(is_equal(nodes, edges1, node_perm, edges2) for node_perm in permutations(nodes))
In [26]:
def count_unique(n):
    nodes, graphs = all_graphs_for(n)
    groups = {}
    merged = [False] * len(graphs)
    for i in range(len(graphs)):
        if merged[i]:
            continue
        merged[i] = True
        groups[i] = {i}
        
        for j in range(i + 1, len(graphs)):
            if merged[j]:
                continue
            if is_isometric(nodes, graphs[i], graphs[j]):
                groups[i].add(j)
                merged[j] = True
    return len(groups)
In [30]:
for i in range(7):
    print(i, count_unique(i))

0 1
1 1
2 1
3 2
4 4
5 12

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-30-68ceb4badcb4> in <module>
      1 for i in range(7):
----> 2     print(i, count_unique(i))

<ipython-input-26-3170bb933d0e> in count_unique(n)
     12             if merged[j]:
     13                 continue
---> 14             if is_isometric(nodes, graphs[i], graphs[j]):
     15                 groups[i].add(j)
     16                 merged[j] = True

<ipython-input-28-f84734544ec3> in is_isometric(nodes, edges1, edges2)
     17 
     18 def is_isometric(nodes, edges1, edges2):
---> 19     return any(is_equal(nodes, edges1, node_perm, edges2) for node_perm in permutations(nodes))

<ipython-input-28-f84734544ec3> in <genexpr>(.0)
     17 
     18 def is_isometric(nodes, edges1, edges2):
---> 19     return any(is_equal(nodes, edges1, node_perm, edges2) for node_perm in permutations(nodes))

<ipython-input-28-f84734544ec3> in is_equal(nodes1, edges1, nodes2, edges2)
     10         for j in range(i + 1, len(nodes1)):
     11             u, v = nodes1[i], nodes1[j]
---> 12             dir1 = direction(nodes1[i], nodes1[j], edges1)
     13             dir2 = direction(nodes2[i], nodes2[j], edges2)
     14             if dir1 != dir2:

<ipython-input-28-f84734544ec3> in direction(u, v, edges)
      2 
      3 def is_equal(nodes1, edges1, nodes2, edges2):
----> 4     def direction(u, v, edges):
      5         if u < v:
      6             return edges[(u, v)]

KeyboardInterrupt:
In [31]:
def count_unique_prog(n):
    nodes, graphs = all_graphs_for(n)
    groups = {}
    merged = [False] * len(graphs)
    for i in range(len(graphs)):
        print(i)
        if merged[i]:
            continue
        merged[i] = True
        groups[i] = {i}
        
        for j in range(i + 1, len(graphs)):
            if merged[j]:
                continue
            if is_isometric(nodes, graphs[i], graphs[j]):
                groups[i].add(j)
                merged[j] = True
    return len(groups)
print(6, count_unique_prog(6))

0

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-31-4f740a75ae7c> in <module>
     17                 merged[j] = True
     18     return len(groups)
---> 19 print(6, count_unique_prog(6))

<ipython-input-31-4f740a75ae7c> in count_unique_prog(n)
     13             if merged[j]:
     14                 continue
---> 15             if is_isometric(nodes, graphs[i], graphs[j]):
     16                 groups[i].add(j)
     17                 merged[j] = True

<ipython-input-28-f84734544ec3> in is_isometric(nodes, edges1, edges2)
     17 
     18 def is_isometric(nodes, edges1, edges2):
---> 19     return any(is_equal(nodes, edges1, node_perm, edges2) for node_perm in permutations(nodes))

<ipython-input-28-f84734544ec3> in <genexpr>(.0)
     17 
     18 def is_isometric(nodes, edges1, edges2):
---> 19     return any(is_equal(nodes, edges1, node_perm, edges2) for node_perm in permutations(nodes))

KeyboardInterrupt:
In [22]:
graphs[7]
Out[22]:
{(0, 1): 1, (0, 2): 1, (1, 2): 1}